# 79. 单词搜索

def exist(board, word):
    ans = []
    used = [[False] * len(board[0]) for _ in range(len(board))]
    def trackback(m, n, used, index, word):
        if ans != []:
            return
        hang = len(board)
        lie = len(board[0])
        if index == len(word):
            ans.append(True)
            return
        if m < 0 or n < 0 or m >= hang or n >= lie or word[index] != board[m][n]:
            return
        if used[m][n] == True:
            return
        used[m][n] = True
        trackback(m - 1, n, used, index + 1, word)
        trackback(m + 1, n, used, index + 1, word)
        trackback(m, n - 1, used, index + 1, word)
        trackback(m, n + 1, used, index + 1, word)
        used[m][n] = False

    for i in range(0, len(board)):
        for j in range(0, len(board[0])):
            trackback(i, j, used, 0, word)
    return ans!=[]

if __name__ == "__main__":
    board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
    word = "ABCCED"
    print(exist(board,word))